package cn.cxq.learning.array;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * 剑指offer
 * 构建乘积数组 相似的企业真题
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：281355
 * 本题知识点： 数组
 *  算法知识视频讲解
 * 题目描述
 * 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。
 * 不能使用除法。（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）
 * 对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。
 * 示例1
 * 输入
 * 复制
 * [1,2,3,4,5]
 * 返回值
 * 复制
 * [120,60,40,30,24]
 */
public class Multiply {

    @Test
    public void test() {
        System.out.println(Arrays.toString(multiply(new int[]{1,2,3,4,5})));
    }

    // O(n) 的解法
    public int[] multiply(int[] A) {

        int[] result = new int[A.length];

        int temp = 1;

        for (int i = A.length - 1; i >= 0; i--) { // 先算出每个结果在下标后半部分的乘积（半成品）
            result[i] = temp;
            temp *= A[i];
        }

        temp = 1;

        for (int i = 0; i < A.length; i++) { //在处理下标前面的乘积
            result[i] = temp*result[i];
            temp*=A[i];
        }

        return result;
    }

    // 时间复杂度 O(n的二次方)
//    public int[] multiply(int[] A) {
//
//        int[] result = new int[A.length];
//
//        for (int i = 0; i < result.length; i++) {
//            result[i] = 1;
//        }
//
//        for (int i = 0; i < A.length; i++) {
//            for (int j = 0; j < A.length; j++) {
//                if (j != i) {
//                    result[i] *= A[j];
//                }
//            }
//        }
//
//        return result;
//    }
}
